Linked List Reversal: Methods to Reverse a Singly Linked List, Implemented Recursively and Iteratively

A singly linked list consists of nodes with a data field and a pointer field (next), starting from a head node, with the tail node's next being None. Reversing a linked list is used in scenarios such as reverse output and palindrome judgment. **Iterative Method**: Traverse the list while maintaining three pointers: `prev` (initially None), `current` (the head node), and `next` (temporary storage). Steps: 1. Save `current.next` to `next`. 2. Reverse `current.next` to point to `prev`. 3. Move `prev` to `current` and `current` to `next`. 4. When `current` is None, return `prev` (the new head). Time complexity: O(n), Space complexity: O(1). Intuitive. **Recursive Method**: Recursively reverse sublists (terminates when the sublist is empty or has one node). After recursion, set `head.next.next = head` and `head.next = None`, then return the new head. Time complexity: O(n), Space complexity: O(n) (due to recursion stack). Concise code. **Comparison**: Iterative method avoids stack overflow risks; recursion relies on the call stack. Key points: - Iterative: Pay attention to pointer order. - Recursive: Clearly define the termination condition.